package algorithm.dynamic_planning.package_learn;

/**
 * @author yuisama
 * @date 2022年12月16日 15:02
 * @description LC-416号问题，分割子数组，背包问题
 * 给定一个可装载sum / 2容量的背包和N个物品，每个物品重量为nums[i]。是否存在一种装法，能够恰好将背包装满
 *
 */
public class Num416_CanPartitionNum {
    // dp[i][j]  = x 表示使用前i件物品，当前背包容量为j时，若x == true，则恰好将背包装满
    // eg : dp[4][9] = true,表示使用前4件物品，恰好可以装满容量为9的背包
    // 所以本问题就是在求dp[N][sum/2]的值
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum % 2 != 0) {
            // 和为奇数，不可能均等划分！
            return false;
        }
        sum = sum / 2;
        // 状态压缩 => 注意dp[i][j]都是从dp[i - 1][..]转移来，因此不用存储物品数量信息
        boolean[] dp = new boolean[sum + 1];
        // base case.容量为0的背包，随便装物品都能装满
        dp[0] = true;
        // 每当i迭代一次,dp[i][j]就向前走一步，即最新的dp[j] == dp[i-1][j]
        for (int i = 1; i <= nums.length; i++) {
            // j此时需要从后向前遍历，因为每个数组只能用一次，避免对其他数字产生干扰
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i - 1] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
                }
            }
        }
        return dp[sum];
    }
}
